Finite or Galois fields (GF) are widely used in many applications, including error-correcting codes, switching theory, and digital signal processing. For example, the Reed-Solomon (RS) error-correcting codes utilize the finite field GF(2m) of 2m elements, where m is a positive integer. These applications usually require to perform the arithmetic operations, which are different from the usual binary arithmetic operations, for the field GF(2m).
Because of their frequent computations, many hardware devices have been implemented to handle the arithmetic operations in hope to compute more efficiently. The systolic architecture, due to its simplicity and regularity, has been successfully used for such a VLSI implementation. The implementation allows simultaneous multiplication and addition operations without a look-up table for the elements of GF(2m). A look-up table is costly when m is large. However, the prior designs are unable to handle computations over dual-basis in Galois fields with a single calculator. An application that requires computing Galois fields over dual-basis needs two distinct product-sum calculators, and thus may double the gate count in the VLSI implementation.
A parallel-in, parallel-out systolic architecture for product-sum computation A*B+C in the Galois field GF(2m) was developed by C. -S. Yea et al. in an article titled “Systolic Multipliers for Finite Fields GF(2m)”, pp. 357–360, VOL. C33, NO. 4, April 1984 of the IEEE Transactions on Computers. Although the proposed architecture was simple and regular enough for VLSI implementation, it can only compute over a singular basis. For applications that utilize dual-basis Galois fields, a VLSI design requires two product-sum calculators to accomplish the computation. This results in a higher gate count and a larger circuitry area, thus a higher manufacture cost.